package com.hc.programming.linked;

import com.hc.programming.bean.ListNode;

import java.util.Arrays;

/**
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * <p>
 * 示例 1：
 * <a href="./删除链表的倒数第N个结点-示例1.png" target="_blank">示例1</a>
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 * 示例 2：
 * 输入：head = [1], n = 1
 * 输出：[]
 * 示例 3：
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 * <p>
 * 提示：
 * 链表中结点的数目为 sz
 * 1 <= sz <= 30
 * 0 <= Node.val <= 100
 * 1 <= n <= sz
 * <p>
 * 进阶：你能尝试使用一趟扫描实现吗？
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/10/23 19:17
 */
public class 删除链表的倒数第N个结点 {
    public static void main(String[] args) {
        System.out.println(removeNthFromEnd(new ListNode(Arrays.asList(1, 2, 3, 4, 5)), 2));
        System.out.println(removeNthFromEnd(new ListNode(Arrays.asList(1)), 1));
        System.out.println(removeNthFromEnd(new ListNode(Arrays.asList(1, 2)), 1));
        System.out.println(removeNthFromEnd(new ListNode(Arrays.asList(1, 2)), 2));
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        return 两次遍历(head, n);
    }

    private static ListNode 两次遍历(ListNode head, int n) {
        if (head == null) return null;
        ListNode node = head;
        int len = 0;
        while (node != null) {
            len++;
            node = node.next;
        }
        if (n == len) return head.next;
        if (len < n) return null;
        node = head;
        for (int i = 0; i < len-n-1; i++) {
            node = node.next;
        }
        node.next = node.next.next;
        return head;
    }
}
